The invention described herein was made by an employee of the United States Government and may be manufactured and used by or for the Government for government purposes without payment of any royalties thereon or therefor.
This invention relates to routing of entities, such as information packets or physically transportable items, from a source to a destination in a network.
Many networks share as a component one or more instances of a xe2x80x9crouting procedurexe2x80x9d by which, in response to a xe2x80x9crouting requestxe2x80x9d that a particular entity be transported from a first node xe2x80x9cAxe2x80x9d to eventually arrive at a second node xe2x80x9cBxe2x80x9d in the network, one or more xe2x80x9clinksxe2x80x9d from a path that connects node A and node B are selected.
As an example, at the network layer 3 in a digital computer or telecom network, these nodes may be data switching routers, and each associated link may be a direct connection between two neighboring routers. The entity to be transported may be a small as a single packet, frame, cell, flow control signal, etc. (collectively referred to herein as xe2x80x9cpacketsxe2x80x9d) or as large as a set of packets in a selected format (delineated by time, by a sequence number or running count of packets routed through a node, by an originating source and/or ultimate destination, by the time the entity was transported from the source node). A particular instance occurs when the routing procedure is resident on a single router or switch, and the procedure is used only to select the next link for the entity to follow on the path to the entity""s ultimate destination B. After the procedure is completed, the entity is transported along the chosen link, and the procedure is repeated at the node at the other end of the chosen link.
Alternatively, the entity may be the contents of a temporally open circuit for which the procedure selects an ordered set of consecutive links from node A to node B. Alternatively, the procedure may be used as part of an intermediate scheme, as in flow control or in an ATM-switched network. Well known routing algorithms include distance vector (Bellman-Ford), RIP, link state, ISIS and OSPF, and are discussed in some detail in Radia Perlman, Interconnections: Bridges and Routers, Addison Wesley Publishing, Reading, Mass., 1992, Chapters 9 and 10.
As another example, the entity may be a physical item to be transported, such as an aircraft or other vehicle, along a path from one waypoint to the next waypoint. More generally, the entity can be any item (data, physical object, etc.) that is to be transported from a source node to a destination node in a network, using a path including one or more links that connect nodes in the network.
More generally, the nodes can be states of the entity, the links are allowed transitions of the entity, and the procedure is used to schedule transitions of entities so that the entities attain their ultimate states. In particular, the invention may be appropriate when it is preferred that no entity visit the same state twice. As a particular example that need not involve transport of the entities, the entities may be physical goods being manufactured or otherwise transformed at one or more nodes, the nodes may represent states of these goods, an ultimate entity destination may be the state of a completed good, and the routing procedure may be a dynamic scheduling algorithm controlling a production schedule or chain for these goods.
A routing procedure can involve techniques from the established field of reinforcement learning, as discussed by R. S. Sutton and A. G. Barto in Reinforcement Learning: An Introduction, MIT Press, Cambridge, Mass., 1998. In a simple instance of this, the routing procedure can be provided with numerical xe2x80x9creward signalsxe2x80x9d from the environment periodically, with the reward signals reflecting values of a cost function. The procedure uses these reward signals together with other received information to statistically determine at run time how, if at all, to modify its response to a given routing request in order to increase the expected value(s) of the reward signals the procedure will receive in the future. A choice by a system""s designer as to how to select or implement the reward signals to be provided to the routing procedure may be determined by what behavior(s) the designer wishes to promote or to discriminate against, among other things. If, for example, the designer wishes to maximize global traffic throughput, a value of throughput, averaged over a selected time interval, may be used to determine the reward signal(s) for the routing procedure.
Routing of entities on a network often relies on a routing procedure from a source A to a destination B that may be characterized as xe2x80x9call-or-nothingxe2x80x9d: if the value of a given cost function associated with following one possible path connecting node A and node B is estimated to be lower than the value of the cost function for any other path considered that connects A and B, only links from the first path are selected, until such time as new cost estimates are available. Adoption of this all-or-nothing approach has several disagreeable consequences.
First, by always selecting links that are part of the same path, the value of the cost function associated with the selected links is likely to increase significantly. For example, this overloading may increase network congestion and/or transportation failure (entity loss or misdelivery) on the chosen link(s). Second, because the value of the cost function associated with the selected links increases so substantially and abruptly, it is likely that the selected links will promptly be de-selected as part of a chosen path, thus producing some instability in the behavior of the network.
Third, the network has no opportunity to make a graceful transition from a first set of links to a second set of links, for example, when one or more links in the first set becomes increasingly costly (or inoperative). Fourth, adoption of an all-or-nothing routing procedure requires xe2x80x9chard-edgedxe2x80x9d use of a cost criterion that allows little or no provision for uncertainty in modeling of the network processes. In particular, discrepancies between estimated and actual values of the cost function may be magnified using such a procedure, due to associated instabilities in the network, and, simultaneously, degradation in the network""s performance associated with any particular discrepancy level may be increased (system xe2x80x9cbrittlenessxe2x80x9d).
What is needed is a routing procedure that selects links from a collection of two or more A-B paths on a network in a manner that does not always choose the same link(s), even for two instances of the procedure that have identical estimated values of the associated cost functions. Preferably, this procedure should permit a graceful transition from one set of links to another set of links (either partly overlapping or completely non-overlapping) as the circumstances of network operation change with time. Preferably, this procedure should be adaptable to separately optimize different portions of the network. Preferably, this procedure should permit compensation for probabilities that a network will behave in one way or another, at a given time or over a succession of times. Preferably, this procedure should be usable in networks where some of the routing decisions are made by different procedures (i.e., two or more independent routing procedures are used), without requiring substantial changes in the underlying protocols and/or formats associated with the entities being transported, and with at most modest increases in communications regarding network status. Preferably, this procedure will not lead to xe2x80x9ccyclesxe2x80x9d, in which an entity visits the same node twice. Preferably, this procedure can be modified so that separate entities moving from node A to node B do not arrive out of order.
These needs are met by the invention, which provides an approach that accounts for link/path traffic and/or link/path costs on a network with N nodes (Nxe2x89xa72). Consider a particular node i in the network that is directly connected to J other nodes, labeled or numbered j=j1, j2, . . . , jJ. A xe2x80x9cbaseline proportion vectorxe2x80x9d p(i;xcexc), having J components, is associated with node i, where p(i;xcexc) is used to determine how to transport an entity, having a characteristic or set of characteristics designated by xcexc, from node i. Examples of such characteristics g include the originating source, the ultimate destination, the routing priority, and the time the entity was last transported from the source node.
In one embodiment of the invention, a J(xcexc)-component xe2x80x9capplied proportion vectorxe2x80x9d p*(i;xcexc) is determined from p(i;xcexc) so that no entity is ever transported from the node i to a connected node j if the jth component p*(i;xcexc)j=0. With this determination employed for all link selections for an entity, that entity will not visit any node more than once before the entity reaches its destination node. In one embodiment of the invention, two more J(xcexc)-component vectors, Target(i;n(xcexc);xcexc) and Actual(i;n(xcexc);xcexc) are computed and used, where n=n(xcexc) is a sequence number or count at the node i that may depend upon one or more of the characteristics xcexc of the entity being transported and the associated routing request. At each node i for an entity with characteristic xcexc, for selected values of n(xcexc), a new determination is made of the i-to-j link, j=jxe2x80x2(xcexc), with the largest value of the difference Target(i;n(xcexc);xcexc)xe2x88x92Actual(i;n(xcexc);xcexc). The entity is transported along the i-to-jxe2x80x2(xcexc) link. The vectors Target(i;n(xcexc);xcexc) and Actual(i;n(xcexc);xcexc)) are computed iteratively from the relations Target(i;n(xcexc);xcexc)=xcex1(xcexc)xc2x7Target(i;n(xcexc)xe2x88x921;xcexc)+xcex2(xcexc)xc2x7p*(i;xcexc) and Actual(i;n(xcexc)+1;xcexc)=xcex1(xcexc)xc2x7Actual(i;n(xcexc);xcexc)+xcex2(xcexc)xc2x7Sent(i;jxe2x80x2(xcexc);n(xcexc);xcexc). Here, xcex1(xcexc) and xcex2(xcexc) are selected real number and Sent(i;jxe2x80x2(xcexc);n(xcexc);xcexc) is a J(xcexc)-component vector with component j=jxe2x80x2(xcexc) having the value 1 and all other components having the value 0. The number J(xcexc) of nodes directly connected to node i, the originating source node A and/or the ultimate destination node B can vary with the characteristic xcexc.
The objective of the invention is to optimize some measure of network performance, such as overall entity throughput, amount of discarded entities, entity errors, misdelivered entities, minimum bandwidth or other corresponding effort required, financial cost of transporting an entity, average or minimum or maximum time delay for entity delivery, priority level for an entity, or some other measure of quality of service (QOS) on the network. Currently, many such measures have associated procedures that are used in actual networks. However, most existing procedures do not provide an optimal performance according to the associated measures.